package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 * https://leetcode-cn.com/problems/unique-binary-search-trees/
 * @version 1.0
 * @date 2021/12/5 23:18
 * 数学知识储备：
 * 令h(0)=1,h(1)=1，卡塔兰数（catalan）满足递归式：
 * h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;
 * 还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1
 * 该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
 */
public class numTrees {
    public static void main(String[] args) {
        System.out.println(numTrees(3));
    }

    // 假设 h(n) 为 n个节点 的二叉搜索数种类。那么，h(0) 表示没有节点时，二叉搜索树的种数为1，h(1) 表示只有一个节点时，二叉搜索树的种数为1。
    // h(n) 中 以 1 为顶点时，左子树就是 h(0)种情况，右边子树就是 h(n-1)种情况，那么以 1 为顶点的二叉搜索树 就有 h(0)*h(n-1) 种
    // h(n) 中 以 2 为顶点时，h(1)*h(n-2) 种
    // ...
    // 这就是 卡特兰数
    static int numTrees(int n) {
        // 需要用 long 类型防止计算过程中的溢出
        long res = 1;
        for (int i = 1; i <= n; i++) {
            res = (4 * i - 2) * res / (i + 1);
        }
        return (int) res;
    }
}
